package com.mgq.algorithm.link;

import com.mgq.algorithm.twotree.TreeNode;

/**
 * @author MaGuangQi
 * 将二叉树压扁
 * @date 2022-02-17 15:58
 **/
public class Flatten_114 {
    public static void flatten(TreeNode root) {
        if(root==null) return;
        //先序遍历
        //打印
        TreeNode leftTmp=root.left;
        TreeNode rightTmp=root.right;
        //把 2指向 3
        root.left=null;
        root.right=leftTmp;
        TreeNode p=root;
        // 把
        //将右树接到左树上.
        while(p.right!=null){
            p=p.right;
        }
        p.right=rightTmp;
        flatten(leftTmp);
        flatten(rightTmp);
    }

    public static void main(String[] args) {
        TreeNode node1=new TreeNode(1);
        TreeNode node2=new TreeNode(2);
        TreeNode node3=new TreeNode(3);
        TreeNode node4=new TreeNode(4);
        TreeNode node5=new TreeNode(5);
        TreeNode node6=new TreeNode(6);
        node1.left=node2;
        node1.right=node5;
        node2.left=node3;
        node2.right=node4;
        node5.right=node6;
        flatten(node1);
    }
}
